#depth first search pseudocode | Explore Tumblr posts and blogs

viswatechynology · 3 years ago

Text

DFS

Depth-First Search Algorithm

The depth-first search or DFS algorithm traverses or explores data structures, such as trees and graphs. The algorithm starts at the root node (in the case of a graph, you can use any random node as the root node) and examines each branch as far as possible before backtracking.

When a dead-end occurs in any iteration, the Depth First Search (DFS) method traverses a network in a deathward motion and uses a stack data structure to remember to acquire the next vertex to start a search.

Following the definition of the dfs algorithm, you will look at an example of a depth-first search method for a better understanding.

Example of Depth-First Search Algorithm

The outcome of a DFS traversal of a graph is a spanning tree. A spanning tree is a graph that is devoid of loops. To implement DFS traversal, you need to utilize a stack data structure with a maximum size equal to the total number of vertices in the graph.

To implement DFS traversal, you need to take the following stages.

Step 1: Create a stack with the total number of vertices in the graph as the size.

Step 2: Choose any vertex as the traversal’s beginning point. Push a visit to that vertex and add it to the stack.

Step 3 — Push any non-visited adjacent vertices of a vertex at the top of the stack to the top of the stack.

Step 4 — Repeat steps 3 and 4 until there are no more vertices to visit from the vertex at the top of the stack.

Step 5 — If there are no new vertices to visit, go back and pop one from the stack using backtracking.

Step 6 — Continue using steps 3, 4, and 5 until the stack is empty.

Step 7 — When the stack is entirely unoccupied, create the final spanning tree by deleting the graph’s unused edges.

Consider the following graph as an example of how to use the dfs algorithm.

Step 1: Mark vertex A as a visited source node by selecting it as a source node.

· You should push vertex A to the top of the stack.

Step 2: Any nearby unvisited vertex of vertex A, say B, should be visited.

· You should push vertex B to the top of the stack.

Step 3: From vertex C and D, visit any adjacent unvisited vertices of vertex B. Imagine you have chosen vertex C, and you want to make C a visited vertex.

· Vertex C is pushed to the top of the stack.

Step 4: You can visit any nearby unvisited vertices of vertex C, you need to select vertex D and designate it as a visited vertex.

· Vertex D is pushed to the top of the stack.

Step 5: Vertex E is the lone unvisited adjacent vertex of vertex D, thus marking it as visited.

· Vertex E should be pushed to the top of the stack.

Step 6: Vertex E’s nearby vertices, namely vertex C and D have been visited, pop vertex E from the stack.

Step 7: Now that all of vertex D’s nearby vertices, namely vertex B and C, have been visited, pop vertex D from the stack.

Step 8: Similarly, vertex C’s adjacent vertices have already been visited; therefore, pop it from the stack.

Step 9: There is no more unvisited adjacent vertex of b, thus pop it from the stack.

Step 10: All of the nearby vertices of Vertex A, B, and C, have already been visited, so pop vertex A from the stack as well.

Now, examine the pseudocode for the depth-first search algorithm in this.

Pseudocode of Depth-First Search Algorithm

Pseudocode of recursive depth-First search algorithm.

Depth_First_Search(matrix[ ][ ] ,source_node, visited, value)

{

If ( sourcce_node == value)

return true // we found the value

visited[source_node] = True

for node in matrix[source_node]:

If visited [ node ] == false

Depth_first_search ( matrix, node, visited)

end if

end for

return false //If it gets to this point, it means that all nodes have been explored.

//And we haven’t located the value yet.

}

Pseudocode of iterative depth-first search algorithm

Depth_first_Search( G, a, value): // G is graph, s is source node)

stack1 = new Stack( )

stack1.push( a ) //source node a pushed to stack

Mark a as visited

while(stack 1 is not empty): //Remove a node from the stack and begin visiting its children.

B = stack.pop( )

If ( b == value)

Return true // we found the value

Push all the uninvited adjacent nodes of node b to the Stack

For all adjacent node c of node b in graph G; //unvisited adjacent

If c is not visited :

stack.push(c)

Mark c as visited

Return false // If it gets to this point, it means that all nodes have been explored.

//And we haven’t located the value yet.

Complexity Of Depth-First Search Algorithm

The time complexity of depth-first search algorithm

If the entire graph is traversed, the temporal complexity of DFS is O(V), where V is the number of vertices.

· If the graph data structure is represented as an adjacency list, the following rules apply:

· Each vertex keeps track of all of its neighboring edges. Let’s pretend there are V vertices and E edges in the graph.

· You find all of a node’s neighbors by traversing its adjacency list only once in linear time.

· The sum of the sizes of the adjacency lists of all vertices in a directed graph is E. In this example, the temporal complexity is O(V) + O(E) = O(V + E).

· Each edge in an undirected graph appears twice. Once at either end of the edge’s adjacency list. This case’s temporal complexity will be O(V) + O (2E) O(V + E).

· If the graph is represented as adjacency matrix V x V array:

· To find all of a vertex’s outgoing edges, you will have to traverse a whole row of length V in the matrix.

· Each row in an adjacency matrix corresponds to a node in the graph; each row stores information about the edges that emerge from that vertex. As a result, DFS’s temporal complexity in this scenario is O(V * V) = O. (V2).

The space complexity of depth-first search algorithm

Because you are keeping track of the last visited vertex in a stack, the stack could grow to the size of the graph’s vertices in the worst-case scenario. As a result, the complexity of space is O. (V).

After going through the complexity of the dfs algorithm, you will now look at some of its applications.

Application Of Depth-First Search Algorithm

The minor spanning tree is produced by the DFS traversal of an unweighted graph.

1. Detecting a graph’s cycle: A graph has a cycle if and only if a back edge is visible during DFS. As a result, you may run DFS on the graph to look for rear edges.

2. Topological Sorting: Topological Sorting is mainly used to schedule jobs based on the dependencies between them. In computer science, sorting arises in instruction scheduling, ordering formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization, and resolving symbols dependencies linkers.

3. To determine if a graph is bipartite: You can use either BFS or DFS to color a new vertex opposite its parents when you first discover it. And check that each other edge does not connect two vertices of the same color. A connected component’s first vertex can be either red or black.

4. Finding Strongly Connected Components in a Graph: A directed graph is strongly connected if each vertex in the graph has a path to every other vertex.

5. Solving mazes and other puzzles with only one solution:By only including nodes the current path in the visited set, DFS is used to locate all keys to a maze.

6. Path Finding: The DFS algorithm can be customized to discover a path between two specified vertices, a and b.

· Use s as the start vertex in DFS(G, s).

· Keep track of the path between the start vertex and the current vertex using a stack S.

· Return the path as the contents of the stack as soon as destination vertex c is encountered.

Finally, in this tutorial, you will look at the code implementation of the depth-first search algorithm.

Code Implementation Of Depth-First Search Algorithm

#include <stdio.h>

#include <stdlib.h>

int source_node,Vertex,Edge,time,visited[10],Graph[10][10];

void DepthFirstSearch(int i)

{

int j;

visited[i]=1;

printf(“ %d->”,i+1);

for(j=0;j<Vertex;j++)

{

if(Graph[i][j]==1&&visited[j]==0)

DepthFirstSearch(j);

}

int main()

{

int i,j,v1,v2;

printf(“\t\t\tDepth_First_Search\n”);

printf(“Enter the number of edges:”);

scanf(“%d”,&Edge);

printf(“Enter the number of vertices:”);

scanf(“%d”,&Vertex);

for(i=0;i<Vertex;i++)

{

for(j=0;j<Vertex;j++)

Graph[i][j]=0;

}

for(i=0;i<Edge;i++)

{

printf(“Enter the edges (V1 V2) : “);

scanf(“%d%d”,&v1,&v2);

Graph[v1–1][v2–1]=1;

}

for(i=0;i<Vertex;i++)

{

for(j=0;j<Vertex;j++)

printf(“ %d “,Graph[i][j]);

printf(“\n”);

}

printf(“Enter the source: “);

scanf(“%d”,&source_node);

DepthFirstSearch(source_node-1);

return 0;

}

#DFS #explain DFS #what is DFS #benifits of DFS #DFS algorithm

1 note · View note

viswatech · 3 years ago

Text

DFS Algorithm

Depth-First Search Algorithm

Following the definition of the dfs algorithm, you will look at an example of a depth-first search method for a better understanding.

Example of Depth-First Search Algorithm

To implement DFS traversal, you need to take the following stages.

Step 1: Create a stack with the total number of vertices in the graph as the size.

Step 2: Choose any vertex as the traversal's beginning point. Push a visit to that vertex and add it to the stack.

Step 3 - Push any non-visited adjacent vertices of a vertex at the top of the stack to the top of the stack.

Step 4 - Repeat steps 3 and 4 until there are no more vertices to visit from the vertex at the top of the stack.

Step 5 - If there are no new vertices to visit, go back and pop one from the stack using backtracking.

Step 6 - Continue using steps 3, 4, and 5 until the stack is empty.

Step 7 - When the stack is entirely unoccupied, create the final spanning tree by deleting the graph's unused edges.

Consider the following graph as an example of how to use the dfs algorithm.

Step 1: Mark vertex A as a visited source node by selecting it as a source node.

· You should push vertex A to the top of the stack.

Step 2: Any nearby unvisited vertex of vertex A, say B, should be visited.

· You should push vertex B to the top of the stack.

Step 3: From vertex C and D, visit any adjacent unvisited vertices of vertex B. Imagine you have chosen vertex C, and you want to make C a visited vertex.

· Vertex C is pushed to the top of the stack.

Step 4: You can visit any nearby unvisited vertices of vertex C, you need to select vertex D and designate it as a visited vertex.

· Vertex D is pushed to the top of the stack.

Step 5: Vertex E is the lone unvisited adjacent vertex of vertex D, thus marking it as visited.

· Vertex E should be pushed to the top of the stack.

Step 6: Vertex E's nearby vertices, namely vertex C and D have been visited, pop vertex E from the stack.

Step 7: Now that all of vertex D's nearby vertices, namely vertex B and C, have been visited, pop vertex D from the stack.

Step 8: Similarly, vertex C's adjacent vertices have already been visited; therefore, pop it from the stack.

Step 9: There is no more unvisited adjacent vertex of b, thus pop it from the stack.

Step 10: All of the nearby vertices of Vertex A, B, and C, have already been visited, so pop vertex A from the stack as well.

Now, examine the pseudocode for the depth-first search algorithm in this.

Pseudocode of Depth-First Search Algorithm

Pseudocode of recursive depth-First search algorithm.

Depth_First_Search(matrix[ ][ ] ,source_node, visited, value)

{

If ( sourcce_node == value)

return true // we found the value

visited[source_node] = True

for node in matrix[source_node]:

If visited [ node ] == false

Depth_first_search ( matrix, node, visited)

end if

end for

return false //If it gets to this point, it means that all nodes have been explored.

//And we haven't located the value yet.

}

Pseudocode of iterative depth-first search algorithm

Depth_first_Search( G, a, value): // G is graph, s is source node)

stack1 = new Stack( )

stack1.push( a ) //source node a pushed to stack

Mark a as visited

while(stack 1 is not empty): //Remove a node from the stack and begin visiting its children.

B = stack.pop( )

If ( b == value)

Return true // we found the value

Push all the uninvited adjacent nodes of node b to the Stack

For all adjacent node c of node b in graph G; //unvisited adjacent

If c is not visited :

stack.push(c)

Mark c as visited

Return false // If it gets to this point, it means that all nodes have been explored.

//And we haven't located the value yet.

Complexity Of Depth-First Search Algorithm

The time complexity of depth-first search algorithm

If the entire graph is traversed, the temporal complexity of DFS is O(V), where V is the number of vertices.

· If the graph data structure is represented as an adjacency list, the following rules apply:

· Each vertex keeps track of all of its neighboring edges. Let's pretend there are V vertices and E edges in the graph.

· You find all of a node's neighbors by traversing its adjacency list only once in linear time.

· The sum of the sizes of the adjacency lists of all vertices in a directed graph is E. In this example, the temporal complexity is O(V) + O(E) = O(V + E).

· Each edge in an undirected graph appears twice. Once at either end of the edge's adjacency list. This case's temporal complexity will be O(V) + O (2E) O(V + E).

· If the graph is represented as adjacency matrix V x V array:

· To find all of a vertex's outgoing edges, you will have to traverse a whole row of length V in the matrix.

· Each row in an adjacency matrix corresponds to a node in the graph; each row stores information about the edges that emerge from that vertex. As a result, DFS's temporal complexity in this scenario is O(V * V) = O. (V2).

The space complexity of depth-first search algorithm

Because you are keeping track of the last visited vertex in a stack, the stack could grow to the size of the graph's vertices in the worst-case scenario. As a result, the complexity of space is O. (V).

After going through the complexity of the dfs algorithm, you will now look at some of its applications.

Application Of Depth-First Search Algorithm

The minor spanning tree is produced by the DFS traversal of an unweighted graph.

1. Detecting a graph's cycle: A graph has a cycle if and only if a back edge is visible during DFS. As a result, you may run DFS on the graph to look for rear edges.

4. Finding Strongly Connected Components in a Graph: A directed graph is strongly connected if each vertex in the graph has a path to every other vertex.

5. Solving mazes and other puzzles with only one solution:By only including nodes the current path in the visited set, DFS is used to locate all keys to a maze.

6. Path Finding: The DFS algorithm can be customized to discover a path between two specified vertices, a and b.

· Use s as the start vertex in DFS(G, s).

· Keep track of the path between the start vertex and the current vertex using a stack S.

· Return the path as the contents of the stack as soon as destination vertex c is encountered.

Finally, in this tutorial, you will look at the code implementation of the depth-first search algorithm.

Code Implementation Of Depth-First Search Algorithm

#include <stdio.h>

#include <stdlib.h>

int source_node,Vertex,Edge,time,visited[10],Graph[10][10];

void DepthFirstSearch(int i)

{

int j;

visited[i]=1;

printf(" %d->",i+1);

for(j=0;j<Vertex;j++)

{

if(Graph[i][j]==1&&visited[j]==0)

DepthFirstSearch(j);

}

int main()

{

int i,j,v1,v2;

printf("\t\t\tDepth_First_Search\n");

printf("Enter the number of edges:");

scanf("%d",&Edge);

printf("Enter the number of vertices:");

scanf("%d",&Vertex);

for(i=0;i<Vertex;i++)

{

for(j=0;j<Vertex;j++)

Graph[i][j]=0;

}

for(i=0;i<Edge;i++)

{

printf("Enter the edges (V1 V2) : ");

scanf("%d%d",&v1,&v2);

Graph[v1-1][v2-1]=1;

}

for(i=0;i<Vertex;i++)

{

for(j=0;j<Vertex;j++)

printf(" %d ",Graph[i][j]);

printf("\n");

}

printf("Enter the source: ");

scanf("%d",&source_node);

DepthFirstSearch(source_node-1);

return 0;

}

#explain DFS #what is DFS #examples of DFS #DFS #DFS algotithm #explain DFS algorithm #benifits of DFS

1 note · View note

felord · 6 years ago

Text

SOLVED:PROJECT 1: SEARCH IN PACMAN

All those colored walls, Mazes give Pacman the blues, So teach him to search. Introduction In this project, your Pacman agent will find paths through his maze world, both to reach a particular location and to collect food efficiently. You will build general search algorithms and apply them to Pacman scenarios. The code for this project consists of several Python files, some of which you will need to read and understand in order to complete the assignment, andsome of which you can ignore. You can download all the code and supporting files as a zip archive. Files you'll edit: search.py Where all of your search algorithms will reside. searchAgents.py Where all of your search-based agents will reside. Files you might want to look at: pacman.py The main file that runs Pacman games. This file describes a Pacman GameState type, which you use in this project. game.py The logic behind how the Pacman world works. This file describes several supporting types like AgentState, Agent, Direction, and Grid. util.py Useful data structures for implementing search algorithms. Supporting files you can ignore: graphicsDisplay.py Graphics for Pacman graphicsUtils.py Support for Pacman graphics textDisplay.py ASCII graphics for Pacman ghostAgents.py Agents to control ghosts keyboardAgents.py Keyboard interfaces to control Pacman layout.py Code for reading layout files and storing their contents Finding a Fixed Food Dot using Search Algorithms In searchAgents.py, you'll find a fully implemented SearchAgent, which plans out a path through Pacman's world and then executes that path step-by-step. The search algorithms for formulating a plan are not implemented -- that's your job. As you work through the following questions, you might find it useful to refer to the object glossary (the second to last tab in the navigation bar above). First, test that the SearchAgent is working correctly by running: python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch The command above tells the SearchAgent to use tinyMazeSearch as its search algorithm, which is implemented in search.py. Pacman should navigate the maze successfully. Now it's time to write full-fledged generic search functions to help Pacman plan routes! Pseudocode for the search algorithms you'll write can be found in the lecture slides. Remember that a search node must contain not only a state but also the information necessary to reconstruct the path (plan) which gets to that state. Important note: All of your search functions need to return a list of actions that will lead the agent from the start to the goal. These actions all have to be legal moves (valid directions, no moving through walls). Hint: Each algorithm is very similar. Algorithms for DFS, BFS, UCS, and A* differ only in the details of how the fringe is managed. So, concentrate on getting DFS right and the rest should be relatively straightforward. Indeed, one possible implementation requires only a single generic search method which is configured with an algorithm-specific queuing strategy. (Your implementation need not be of this form to receive full credit). Hint: Make sure to check out the Stack, Queue and PriorityQueue types provided to you in util.py!Question 1 (2 points) Implement the depth-first search (DFS) algorithm in the depthFirstSearch function in search.py. To make your algorithm complete, write the graph search version of DFS, which avoids expanding any already visited states. Your code should quickly find a solution for: python pacman.py -l tinyMaze -p SearchAgent python pacman.py -l mediumMaze -p SearchAgent python pacman.py -l bigMaze -z .5 -p SearchAgent The Pacman board will show an overlay of the states explored, and the order in which they were explored (brighter red means earlier exploration). Is the exploration order what you would have expected? Does Pacman actually go to all the explored squares on his way to the goal? Hint: If you use a Stack as your data structure, the solution found by your DFS algorithm for mediumMazeshould have a length of 130 (provided you push successors onto the fringe in the order provided by getSuccessors; you might get 244 if you push them in the reverse order). Is this a least cost solution? If not, think about what depth-first search is doing wrong. Read the full article

0 notes

essayyard-blog · 6 years ago

Text

Programming Question Part 1ProblemDevelop a simple Python program to demonstrate understanding of using the

New Post has been published on https://www.essayyard.com/programming-question-part-1problemdevelop-a-simple-python-program-to-demonstrate-understanding-of-using-the/

Programming Question Part 1ProblemDevelop a simple Python program to demonstrate understanding of using the

Part 1ProblemDevelop a simple Python program to demonstrate understanding of using the Tkinter module to design a simple widget and configure it using the layout manager. Then add an event handler that will accept text input to the button and display the content of the text when using the mouse to click on the “click here” button.The program must have the following:Documentation Guidelines:Use good programming style (e.g., indentation for readability) and document each of your program parts with the following items (the items shown between the ” angle brackets are only placeholders. You should replace the placeholders and the comments between them with your specific information). Your cover sheet should have some of the same information, but what follows should be at the top of each program’s sheet of source code. Some lines of code should have an explanation of what is to be accomplished, this will allow someone supporting your code years later to comprehend your purpose. Be brief and to the point. Start your design by writing comment lines of pseudocode. Once that is complete, begin adding executable lines. Finally run and test your program.Deliverable(s):Your deliverable should be a Word document with screenshots showing the source code and running results, and discuss the issues that you had for this project related to AWS and/or Python IDE and how you solved them for all of the programs listed above as well as the inputs and outputs from running them. Submit a cover sheet with the hardcopy of your work.part 2For this assignment, you will develop working examples of a graphical user interface (GUI) and event handling and that demonstrate the following:Be sure to include a brief narrative of your code where you explain what the code is doing.Documentation Guidelines:Use good programming style (e.g., indentation for readability) and document each of your program parts with the following items (the items shown between the ” angle brackets are only placeholders. You should replace the placeholders and the comments between them with your specific information). Your cover sheet should have some of the same information, but what follows should be at the top of each program’s sheet of source code. Some lines of code should have an explanation of what is to be accomplished, this will allow someone supporting your code years later to comprehend your purpose. Be brief and to the point. Start your design by writing comment lines of pseudocode. Once that is complete, begin adding executable lines. Finally run and test your program.Deliverable(s):Your deliverable should be a Word document with screenshots showing the GUI and event handling you have created. Also, discuss the issues that you had for this project related to AWS and/or Python IDE and how you solved them for all of the programs listed above as well as the inputs and outputs from running them. Submit a cover sheet with the hardcopy of your work.Part 3Write a Python program using the Python IDE based on recursion with trees that is both depth first and breadth first searches.The Python program to be developed will demonstrate the use of both depth-first (DFS) and breadth-first (BFS) searches. A tree node structure will be developed that will be used both for DFS and BFS searches. The program will apply recursion both for the DFS and BFS searches to completion of the entire DFS and BFS. Also, the Python program will provide as output some of the intermediate nodes that are transverse during the execution of the DFS and BFS. This output of the intermediate nodes searched will demonstrate the different paths executed during a DFS versus BFS.ProblemDevelop functions to demonstrate understanding of implementing a recursive depth first search (DFS) and an iterative breadth first search (BFS) in Python using a simple graph made of nodes. This example will use nodes A, B, C, D, and E connected as follows: A —– / | B-D-C | | / | E —–The program must have the following:Documentation Guidelines:Use good programming style (e.g., indentation for readability) and document each of your program parts with the following items (the items shown between the ” angle brackets are only placeholders. You should replace the placeholders and the comments between them with your specific information). Your cover sheet should have some of the same information, but what follows should be at the top of each program’s sheet of source code. Some lines of code should have an explanation of what is to be accomplished, this will allow someone supporting your code years later to comprehend your purpose. Be brief and to the point. Start your design by writing comment lines of pseudocode. Once that is complete, begin adding executable lines. Finally run and test your program.Deliverable(s):Your deliverable should be a Word document with screenshots showing the source code and running results, and discuss the issues that you had for this project related to AWS and/or Python IDE and how you solved them for all of the programs listed above as well as the inputs and outputs from running them. Submit a cover sheet with the hardcopy of your work.Part 4Two user-defined classes are recommended: class Transaction, and class BankStatement. A main() function will be required that declares a BankStatement object and Transaction objects and then performs operations as shown in the example driver main function below. The BankStatement object (called myStatement in the example main() shown later) contains a container of Transaction objects along with other record-keeping data fields. This is yet another example of the Containment/Composition (a.k.a., “Has-A”) relationship that can exist between classes/objects.The Transaction class is used to create deposit and withdrawal objects. It contains a constructor for initialization. This constructor has three defaulted parameters to facilitate the user declaring transactions and passing appropriate initial data member values as parameters to this constructor or accepting one or more of its defaulted initializer values. It is certainly legal, and perhaps desirable, to also have a LoadTransaction() method that would take inputs from the keyboard on an interactive basis. This, in conjunction with a menu, is a desirable addition but not required for this exercise. The main() driver function shows a partial batch (i.e., hard-coded) implementation rather than the, perhaps, more desirable interactive implementation. See your instructor for any specific additional requirements.# Python model of a bank transaction which can be either# A deposit or a withdraw## Filename: transaction.pyclass Transaction: def __init__(self, inAmount = 0.0, inCode = ‘D’, inNote = “No note”): self.__Amount = inAmount if inAmount >= 0.0 else 0.0 self.__Code = inCode if inCode == ‘D’ or inCode == ‘W’ else ‘D’ self.__Note = inNote if len(inNote) > 0 else “No note” def setAmount(self, newAmount): self.__Amount = newAmount if newAmount >= 0.0 else self.__Amount def getAmount(self): return self.__Amount def setCode(self, newCode): self.__Code = newCode if newCode == ‘W’ or newCode == ‘D’ else self.__Code def getCode(self): return self.__Code def setNote(self, newNote): self.__Note = newNote if len(newNote) > 0 else self.__Note def getNote(self): return self.__Note def loadTransaction(self): self.setAmount(float(input(“Enter transaction amount(DD.CC), $ “))) self.setCode(input(“Enter transaction code (‘W’ or ‘D’), “)) self.setNote(input(“Enter purpose of transaction, “))The BankStatement class contains two list containers of Transaction objects, a list container of float values, some BankStatement support data fields, and the required methods to manipulate selected data fields, insert transactions, arrange (i.e., sort) the contained transaction objects, and print them.# Python model of a bank statement capable of# holding and managing multiple bank transactions## Filename: bankStatement.pyfrom transaction import Transactionclass BankStatement: def __init__(self, begBal = 0.0, endBal = 0.0): self.__TransactionLog = [] self.__ArrangedLog = [] self.__RunningBalLog = [] self.__BegBal = begBal self.__EndBal = endBal self.__NumEntries = 0 self.__NumDeposits = 0 self.__NumWithdrawals = 0 def setBegEndBals(self, balance): self.__BegBal = self.__EndBal = balance def getBegBal(self): return self.__BegBal def getEndBal(self): return self.__EndBal def getNumEntries(self): return self.__NumEntries def getNumDeposits(self): return self.__NumDeposits def getNumWithdrawals(self): return self.__NumWithdrawals def insertTransaction(self, transaction): self.__Transactionlog.append(transaction) # Update __RunningBalLog, increment __NumEntries and increment either # __NumDeposits or __NumWithdrawals depending upon whether transaction is a deposit # or a withdrawal def displayResults(self): # Displays __BegBal, __TransactionLog list, __RunningBal list, and final stats (i.e., __EndBal, total transactions, number of deposits and number of withdrawls) # See example output def arrangeTransactions(self): # Builds __ArrangedLog list from __TransactionLog list def printArranged(self): # Displays the __ArrangedLog listThe declared classes and their contents are a starting point for the program. You may not need all the class members described above. Do not feel bound to implement this program using the exact methods and/or data fields given. The primary objective is for you to solve the problem of providing a bank statement to the bank’s customers using O-O programming techniques. HOWEVER, if you deviate from the above design be sure to fully document your design! If in doubt as to whether your deviation violates the intent of this exercise, ask your instructor.In the interest of sound software engineering practice, make sure to validate the values provided to the constructor method of class BankStatement. For invalid values you may choose to completely reject the passed in values and set the data fields to some default (but valid) values. In either case you should also display an error message.Below is a non-interactive(i.e., batch), main driver test function that will confirm to you and your instructor that the program operates as expected. Use the transaction objects given as data for your final submission of the program.def main(): # NOTE THIS IS A NON-INTERACTIVE DRIVER! myStatement = BankStatement() myStatement.setBegEndBals(15.92); # Sets beginning AND ending balance data fields # Declare some transaction objects T1 = Transaction() # TEST DATA T1.setAmount (123.56) T1.setCode(‘D’) T1.setNote(“CTPay”) T2 = Transaction(153.86, ‘W’,”Rent”) T3 = Transaction() T3.setAmount(75.56) T3.setCode(‘D’) T3.setNote(“Tips”) T4 = Transaction(12.56, ‘D’,”Gift”) T5 = Transaction() T5.setAmount(73.74) T5.setCode(‘W’) T5.setNote(“Date”) T6 = Transaction(145.75, ‘D’,”Loan”) T7 = Transaction() T7.setAmount(40.00) T7.setCode(‘W’) T7.setNote(“Loan Payment”) T8 = Transaction(21.74, ‘W’, “Groceries”) # Now insert the transaction objects into the bank statement myStatement.enterTransaction(T1) # Enter transactions into the myStatement.enterTransaction(T2) # BankStatement object # Six more transactions entered…………………………………………………………… ……………………………………………………………………………………………… # continue # Manipulate the bank statement myStatement.displayResults() myStatement.arrangeTransactions() myStatement.printArranged()The following is a look at what the output might look like from the method, displayResults(). The beginning balance was: $15.92 Transaction: 1 was a D amount: $123.56 for CTPay Running Bal: $139.48 Transaction: 2 was a W amount: $153.86 for Rent Running Bal: $-14.38 OVERDRAWN etc., for the other transactions……….…………………………………………………… …….………………………………………………………………………………………. The ending balance is: $84.01 The number of Transactions is: 8 The number of Deposits is: 4 The number of Withdrawals is: 4The following is the result after calling the arrangeTransactions() and printArranged() methods in the BankStatement class. Printing the Deposits and Withdrawals as a group: Transaction was a D amount: $123.56 for CTPay Transaction was a D amount: $75.56 for Tips Transaction was a D amount: $12.56 for Gift Transaction was a D amount: $145.75 for Loan Transaction was a W amount: $153.86 for Rent Transaction was a W amount: $73.74 for Date Transaction was a W amount:$40.00 for Loan Payment Transaction was a W amount: $21.74 for GroceriesTo build the ArrangedLog container in method, arrangeTransactions(), the following strategy is recommended: 1. Traverse the TransactionLog container checking each cell to determine if it is a deposit (‘D’) or withdrawal (‘W’): Loop for number of entries in the TransactionLog if TransactionLog[i].getCode() == ‘D’: append transaction in TransactionLog[i] to next open cell in list container, ArrangedLog 2. In another loop (very similar to the loop above), go back to the beginning of the TransactionLog container and check for all the ‘W’s and copy (i.e., append) them to the ArrangedLog container following the deposits.Now the method, printArranged(), just needs to loop through its entries and display the contents of the ArrangedLog container as shown above.Notice that the methods of an object contained within a containment object are accessed with the selection operator just as though you had the name of the object. However, inside the BankStatement object (myStatement), all you have access to is a container of Transaction objects — not their individual names — hence the TransactionLog[i].getNote() notation.Deliverable(s)Your deliverable should be a Word document with screenshots showing the source code and running results. If the source code is too long, you may insert your source code files as Packages into the Word document. You may also login to the class by using a browser in the AWS, and upload your source code directly. Submit a cover sheet with the hardcopy of your work.

#Programming assignment help|Programming coursework help|Programming essay help|Programming homework help|Programming online class help

0 notes

just4programmers · 7 years ago

Text

Best Books for Machine Learning and Artificial Intelligence

Here you will get list of best books for Machine Learning and Artificial Intelligence that are useful for beginners and intermediates.

Hope you all are doing good. We are again here in front you all with another successive post on Machine Learning. We almost have covered the theoretical portion of the course and will be doing the hands-on practical soon. We all know that there are plenty of resources on the internet that we can use to study and learn almost anything. But again availability of the contents in such a humongous amount haunts the learners that where to start their journey and very often a learner ends up confused and irritated. Great scholars suggest reading books, ain’t they? So why don’t we take the easier path? While the internet is full of plenty of choices that seem very confusing for a novice, we would suggest to start the journey with conventional steps, of course books.

Again you guys do not really worry or need to wander here and there in search of books neither you have to ask someone else’s suggestion for what book to have. Here we have complied a list of some useful books that will give a kick-start to your effort towards data sciences and analytics also on the other hand are interesting to read. Moreover keeping in mind our readers convenience, we’ve also provided the links from where you can order books of your choice without even stepping out of the comfort of your home. So without talking much let’s get started and step toward the list we have compiled for you.

Best Books for Machine Learning (ML)

The Elements of Statistical Learning

As the name itself suggests, this book aims at explaining the algorithms of machine learning mathematically with a tint of statistics. The three authors are Trevor Hastie, Robert Tibshirani and Jerome Friedman has emphasized on explaining the logic behind the machine learning algorithms with the help of mathematical derivations.

Note: If you have a good grasp of linear algebra, we would suggest to go with this book.

Python Machine Learning by Example

Instead you can buy this book written by Yuxi (Hayden) Liu. With this book you will be able to learn the fundamentals of machine learning and would be able to build your own intelligent applications.

Note: Please note there is no pre-requisite to start with this book. Even a person with zero knowledge about machine learning can easily get a grasp over the course.

Learning from Data

This very books provide a simplified understanding of the complex areas of machine learning. Instead of lengthy explanations, small and to-the point explanation is being provided by Yaser Abu Mostafa, Malik Magdon Ismail and Hsuan-Tien Lin. We would suggest this book as a good means to learn and apply the principles of machine learning for the beginners.

Moreover in addition to the book reading you can also refer to online tutorials by Yaser Abu Mostafa.

Programming Collective Intelligence

This book popularly known as PCI in the world of machine learning is said to have all that requires to start learning machine learning. It is believed that this book was written long before the evolution of machine learning as we see it today, but to our surprise, the topics and chapters discussed entirely relate to the version of machine learning we have today.

We strongly recommend this book to every aspiring data scientist, ml enthusiast and even folks who are into machine learning since quite a few time. We bet you won’t regret giving this book a try.

Machine Learning by Tom Mitchell

After reading the book mentioned just above, we would recommend you to give this too a try. Tom has tried to make his readers understand the concept of machine learning with the help of pseudocodes and case studies. You will also find some interesting basic examples to understand the algorithms with ease.

Best Books for Artificial Intelligence (AI)

Artificial Intelligence: A Modern Approach

This book is considered as the holy book for understanding the immense field of AI. Peter Norvig and Stuart Russell worked together to make this art happen. This book is suited to the people new to AI. Not only this provides an overview about AI but also covers some advanced topics like search algorithms, working with logic, machine learning, language processing, etc.

Paradigm of Artificial Intelligence Programming

This book too is written by Peter Norvig. This book primarily aims at teaching its readers the common lisp techniques to build robust AI systems. Instead of just teaching theory, in this book Norvig has put more emphasis on the practical part to let his readers develop programs and systems at their own. If a personnel want to make his/her career in the AI domain, this book is worth giving a shot.

Artificial Intelligence for Humans

Jeff Heaton, the author of this book aims to teach his readers the basic AI algorithms like clustering, error calculation, linear regression, etc. This book is well equipped with good examples and relevant test cases. Moreover this book demands good grasp on mathematics in order to understand the equations described.

A First Course in Artificial Intelligence

This book is an introductory step towards AI and written by Deepak Khemani. This book is written in such a manner that a person from non-programming background can also understand the concepts easily. Although the advanced topics are not explained into depth, but the overall structure of the book is acceptable. The books explains the classical methods and the updated concepts as well.

Any doubts or suggestions are welcomed in the comment section below. Also let us know if there is any other best books for machine learning and artificial intelligence you have read and is worth mentioning in the list.

The post Best Books for Machine Learning and Artificial Intelligence appeared first on The Crazy Programmer.

#The Crazy Programmer

0 notes